﻿#light

module FiniteStateMachineFSharpMethod

open System
open System.Collections.Generic
open System.Runtime.InteropServices

type fsmType = 
    { 
        pattern : string;
        content : string;
        states : int[,];
        stateDimensionCoincidence : int;
        initialPosition : int; 
        positions : List<int>;
        contentLength : int
    }

let constructStates(pattern : string) : int[,]=
    let stateDimensionCoincidence = pattern.Length
    let states = Array2D.zeroCreate<int> 65535 stateDimensionCoincidence

    for i = 0 to stateDimensionCoincidence - 1 do
        states.[(int)pattern.[0], i] <- 1

    for i = 1 to stateDimensionCoincidence - 1 do
        let currentState = states.[(int)pattern.[i], i]
        if not (currentState = 0) then
            states.[(int)pattern.[currentState], i + 1] <- currentState + 1
        states.[(int)pattern.[i], i] <- i + 1
    states

let solve(fsm : fsmType) =
    let mutable state = 0
    let mutable currentPosition = 0
    while currentPosition < fsm.contentLength do
        state <- fsm.states.[(int)fsm.content.[currentPosition], state]
        if state = fsm.stateDimensionCoincidence then
            fsm.positions.Add(fsm.initialPosition + currentPosition)
            state <- 0
        currentPosition <- currentPosition + 1